"""
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。


示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false



提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
"""


class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # 先判断是否为偶数，奇数则返回false
        if len(s) % 2 != 0:
            return False

        # 使用栈
        stack = []
        # 做一个映射，方便后续查找
        mapping = {')': '(', ']': '[', '}': '{'}

        # 开始入栈
        for char in s:
            if char in '({[':
                stack.append(char)
            else:
                if not stack:
                    return False
                # 开始出栈
                top = stack.pop()
                if mapping[char] != top:
                    return False
        return not stack


def test():
    sol = Solution()
    test_cases = [
        ("()", True),  # 示例1
        ("()[]{}", True),  # 示例2
        ("(]", False),  # 示例3
        ("([])", True),  # 嵌套括号
        ("([)]", False),  # 错误嵌套顺序
        ("[", False),  # 单一左括号
        ("]", False),  # 单一右括号
        ("(())", True),  # 多层嵌套
        ("[{}]", True),  # 混合括号
        ("([{)]", False),  # 半匹配状态
        ("", True),  # 空字符串（题目要求长度>=1，但应处理）
        ("}{", False)  # 只有右括号开头
    ]

    for s, expected in test_cases:
        result = sol.isValid(s)
        print(f"输入: '{s}'\t预期: {expected}\t实际: {result}\t{'✓' if result == expected else '✗'}")


test()
